package com.lwl.Algorithmic_data_structure.class22暴力递归2动态规划5;

/**
 * @author lwl
 * @Description 给你一个一维数组表示不重复的硬币值，以及一个目标值，请你求出使用硬币组成目标值所使用的最小硬币数
 * @date 2023/6/13 21:27
 */
public class Code02MinCoinsNoLimit {

    static public int minCoinsNoLimit3(int[] coins, int target) {
        int N = coins.length;
        int[][] dp = new int[N + 1][target + 1];
        dp[N][0] = 0;
        for (int i = 1; i <= target; i++) {
            dp[N][i] = Integer.MAX_VALUE;
        }
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= target; rest++) {
                // 当前选择使用0张，直接用下一种硬币
                dp[index][rest] = dp[index + 1][rest];
                // 当前选择使用1张
                // Q 为什么选择使用1张的？
                // A 这个其实根据表结构依赖来看的，用两张，三张都可以；因为使用一张也是依赖使用两张。。。
                if (rest - coins[index] >= 0 &&
                        dp[index][rest - coins[index]] != Integer.MAX_VALUE) {
                    dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - coins[index]] + 1);
                }
            }
        }
        return dp[0][target];
    }

    static public int minCoinsNoLimit2(int[] coins, int target) {
        int N = coins.length;
        int[][] dp = new int[N + 1][target + 1];
        dp[N][0] = 0;
        for (int i = 1; i <= target; i++) {
            dp[N][i] = Integer.MAX_VALUE;
        }
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= target; rest++) {
                dp[index][rest] = Integer.MAX_VALUE;
                // 每次测试使用i枚当前硬币的使用硬币总数，取最小值
                for (int i = 0; i <= (rest / coins[index]); i++) {
                    int p = dp[index + 1][rest - ((i) * coins[index])];
                    if (p != Integer.MAX_VALUE) {
                        p += i;
                    }
                    dp[index][rest] = Math.min(p, dp[index][rest]);
                }
            }
        }
        return dp[0][target];
    }

    static private int minCoinsNoLimit(int[] coins, int target) {
        int res = process(coins, 0, target);
        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;
    }

    private static int process(int[] coins, int index, int rest) {
        if (index == coins.length) {
            if (rest == 0) {
                return 0;
            }
            return Integer.MAX_VALUE;
        }
        int res = Integer.MAX_VALUE;
        // 每次测试使用i枚当前硬币的使用硬币总数，取最小值
        for (int i = 0; i <= (rest / coins[index]); i++) {
            int p = process(coins, index + 1, rest - ((i) * coins[index]));
            if (p != Integer.MAX_VALUE) {
                p += i;
            }
            res = Math.min(p, res);
        }
        return res;
    }

}
